package 力扣._124_二叉树中的最大路径和;

import 力扣.公用数据结构.TreeNode;

import java.util.Arrays;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    int max = Integer.MIN_VALUE;

    // 返回从root的左右子树出发的最大路径和
    int[] dfs(TreeNode root) {
        if (root == null)
            return new int[]{0, 0};

        int[] l = dfs(root.left);
        int[] r = dfs(root.right);
        int max_l = Math.max(l[0], l[1]);
        max_l = Math.max(max_l, 0);
        int max_r = Math.max(r[0], r[1]);
        max_r = Math.max(max_r, 0);

        max = Math.max(max, max_l + max_r + root.val);

        return new int[]{root.val + max_l, root.val + max_r};

    }

    public int maxPathSum(TreeNode root) {
        // 从该节点出发，左子树+右子树+当前节点的最大值
        dfs(root);
        return max;

    }
}